package cn.jietuo.leetcode.array;

class Exercise2 {
    public int searchInsert(int[] nums, int target) {
        // 使用二分查找的方式
        // 如果有，则返回数组下标
        int result = binarySearch(nums,0,nums.length - 1,target);
        return result;
    }

    public int binarySearch(int[] nums,int start,int end,int target){
        if(start > end){
            return -1;
        }
        if(start == end){
            if(nums[start] == target){
                return start;
            }else if(nums[start] > target){
               return start == 0 ? 0:start -1;
           }else{
               return start + 1;
           }
        }
        int mid = start + ((end - start ) >> 1);
        if(mid >= start && mid <= end){
            if(target == nums[mid]){
                return mid;
            }else if(target < nums[mid]){
                return binarySearch(nums,start,mid -1,target);
            }else{
                return binarySearch(nums,mid + 1,end,target);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Exercise2 e = new Exercise2();
        int[] nums = new int[]{1,3,5,6};
        int target = 5;
        int i = e.searchInsert(nums, target);
        System.out.println(i);
    }
}